package ooday01;

import java.util.Arrays;

public class arrtest {
    public static void main(String[] args) {
        int []arr={5,7,3,1,6,9,4,2,8,0};
        System.out.println(Arrays.toString(arr));
        System.out.println();
//        for (int i = 0; i <arr.length-1 ; i++) {
//            for (int j = 0; j < arr.length-i-1 ; j++) {
//                if (arr[j]>arr[j+1]){
//                    int t=arr[j];
//                    arr[j]=arr[j+1];
//                    arr[j+1]=t;
//                }
//            }
//        }
//        System.out.println(Arrays.toString(arr));

//        for (int i = 0; i < arr.length-1; i++) {
//            for (int j = i+1; j < arr.length; j++) {
//                if (arr[i]>arr[j]){
//                    int t=arr[i];
//                    arr[i]=arr[j];
//                    arr[j]=t;
//                }
//            }
//        }
//        System.out.println(Arrays.toString(arr));
//        for (int i = 1; i <arr.length ; i++) {
//            for (int j = i; j >0 ; j--) {
//                if (arr[j]<arr[j-1]){
//                    int t=arr[j];
//                    arr[j]=arr[j-1];
//                    arr[j-1]=t;
//                }else {
//                    break;
//                }
//            }
//        }
//        System.out.println(Arrays.toString(arr));
//        for (int gap = arr.length/2; gap >0 ; gap/=2) {
//            for (int i = gap; i <arr.length ; i++) {
//                for (int j = i-gap; j >=0 ; j-=gap) {
//                    if (arr[j]>arr[j+gap]){
//                        int t=arr[j];
//                        arr[j]=arr[j+gap];
//                        arr[j+gap]=t;
//                    }
//                }
//            }
//        }
//        System.out.println(Arrays.toString(arr));
//        System.out.println(Arrays.toString(Merge(arr,0,arr.length-1)));

    }
    public static int[] Merge(int[] arr,int start,int end){
        if (start==end){
            return new int[]{arr[start]};
        }
        int mid=start+(end-start)/2;
        int[] leftArr=Merge(arr,start,mid);
        int[] rightArr=Merge(arr,mid+1,end);
        int[] newArray=new int[leftArr.length+rightArr.length];
        int l=0,r=0,n=0;
        while (l< leftArr.length&&r<rightArr.length){
            newArray[n++]=leftArr[l]<=rightArr[r]?leftArr[l++]:rightArr[r++];
        }
        while (l<leftArr.length){
            newArray[n++]=leftArr[l++];
        }
        while (r<rightArr.length){
            newArray[n++]=rightArr[r++];
        }
        return newArray;
    }
}
